package com.zhaopin.theswordreferstooffer;

import java.util.Objects;

/**
 * @author yin.peide
 * @date 2021-06-09 20:09
 * 面试题17： 合并两个排序的链表
 *
 * TODO 后期再加工 ，比较费解
 */
public class Offer17 {

    public static void main(String[] args) {
        LinkedNode17 l9 = new LinkedNode17(9);
        LinkedNode17 l7 = new LinkedNode17(7);
        LinkedNode17 l5 = new LinkedNode17(5);
        LinkedNode17 l3 = new LinkedNode17(3);
        LinkedNode17 l1 = new LinkedNode17(1);
        l1.next = l3;
        l3.next = l5;
        l5.next = l7;
        l7.next = l9;


        LinkedNode17 l10 = new LinkedNode17(10);
        LinkedNode17 l8 = new LinkedNode17(8);
        LinkedNode17 l6 = new LinkedNode17(6);
        LinkedNode17 l4 = new LinkedNode17(4);
        LinkedNode17 l2 = new LinkedNode17(2);
        l2.next = l4;
        l4.next = l6;
        l6.next = l8;
        l8.next = l10;
        merge(l1, l2);
    }


    public static LinkedNode17 merge(LinkedNode17 link1, LinkedNode17 link2) {
        //新建一个头节点，用来存合并的链表。
        LinkedNode17 head = new LinkedNode17(-1);
        head.next = null;
        LinkedNode17 root = head;
        while (link1 != null && link2 != null) {
            if (link1.value < link2.value) {
                head.next = link1;
                head = link1;
                link1 = link1.next;
            } else {
                head.next = link2;
                head = link2;
                link2 = link2.next;
            }
        }
        //把未结束的链表连接到合并后的链表尾部
        if (link1 != null) {
            head.next = link1;
        }
        if (link2 != null) {
            head.next = link2;
        }
        return root.next;
    }

}

class LinkedNode17 {
    int value;
    LinkedNode17 next;

    public LinkedNode17(int value) {
        this.value = value;
    }
}
